import java.util.ArrayList;

/**
 * 给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字，
 * 例如，给出的三角形如下：
 * [[20],[30,40],[60,50,70],[40,10,80,30]]
 * 最小的从顶部到底部的路径和是20 + 30 + 50 + 10 = 110。
 *
 * https://www.nowcoder.com/practice/2b7995aa4f7949d99674d975489cb7da?tpId=46&tqId=29060&tPage=2&rp=2&ru=/ta/leetcode&qru=/ta/leetcode/question-rankin
 */
public class Test {
    public static int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if (triangle == null) return 0;

        int row = triangle.size(); // 行数

        ArrayList<ArrayList<Integer>> minSum = new ArrayList<>();
        for (int i = 0; i < row; i++) {
            minSum.add(new ArrayList<>());
        }
        // 初始化F[0][0]
        minSum.get(0).add(triangle.get(0).get(0));

        for (int i = 1; i < row; ++i) {
            int curSum;
            for (int j = 0; j <= i; ++j) {
                if (j == 0)
                    curSum = minSum.get(i - 1).get(0);
                else if (j == i)
                    curSum = minSum.get(i - 1).get(j - 1);
                else
                    curSum = Math.min(minSum.get(i - 1).get(j), minSum.get(i - 1).get(j - 1));

                minSum.get(i).add(curSum + triangle.get(i).get(j));
            }
        }
        int result = minSum.get(row-1).get(0);
        for (int i = 1; i < row; i++) {
            result = Math.min(result,minSum.get(row-1).get(i));
        }
        return result;
    }

    public static void main(String[] args) {
        // [[20],[30,40],[60,50,70],[40,10,80,30]]
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();

        // [20]
        ArrayList<Integer> list1 = new ArrayList<>();
        list1.add(20);

        // [30,40]
        ArrayList<Integer> list2 = new ArrayList<>();
        list2.add(30);
        list2.add(40);

        // [60,50,70]
        ArrayList<Integer> list3 = new ArrayList<>();
        list3.add(60);
        list3.add(50);
        list3.add(70);

        // [40,10,80,30]
        ArrayList<Integer> list4 = new ArrayList<>();
        list4.add(40);
        list4.add(10);
        list4.add(80);
        list4.add(30);

        // [[20],[30,40],[60,50,70],[40,10,80,30]]
        list.add(list1);
        list.add(list2);
        list.add(list3);
        list.add(list4);


        System.out.println(minimumTotal(list)); // 110
    }
}
